Dijkstra

Dijkstra算法概念： 基本思想：由近到远把所有点的最短路径算出来。 算法解析：从起点向四周辐射，由近到远一层一层遍历所有的点，直到包含目标点所在层级。然后将所有可行路径进行计算比较，筛选出绝对最佳路径。 优点：最终得到的路径一定是最佳路径。 缺点：因为Dijkstra算法需要遍历所有的点，所以程序运行时间较长。

Dijkstra算法过程讲解： 情景假设：从起点开始

1.每次走一格，不能跨格 2.共有8个相邻栅格可以走 3.若走（上/下/左/右）计路程为：2 4.若走（左上/左下/右下/右上）计路程为：3

5.设置两个列表（或者数组） openlist=[ ]        ——存放待确定路径的点 closedlist=[ ]    ——存放已确定路径的点 6.每个点都记录自己的父节点，下标表示 7.为了方便讲解 起点称S点 相邻8个点以A-H称呼 8.已放进closedlist的点不走，因已确定路径

具体过程：

①：起点为S点，计算周围点，父节点为S ②：取一个最小值的点作第二步中心点；从openlist取出，放入closedlist计算中心点周围8个点，累计路程；若点已存在openlist，取路程小的方案。 ③：取一个最小值的点作第三步中心点，重复第二步步骤。 ④：取一个最小值的点作第四步中心点，重复步骤。 ⑤：取一个最小值的点作第五步中心点，重复步骤。 ⑥：取一个最小值的点作第六步中心点，重复步骤。

 ......重复步骤

 伪代码：

获取起点坐标、目标点坐标，把起点放进openlist while (openlist不为空列表) {    取openlist中路程最小的点为中心点，从openlist剔除，放入closedlist     if (中心点是目标点)         {从目标点开始通过父节点反推，提取出路径，break跳出循环}     else         {遍历相邻的八个点             {if(点已存在closedlist中  or  遇到障碍物 )                 {跳过，不计算这个点}             else                 {累计路径                 if(点已存在openlist中)                     if(累计路程 0: pygame.draw.circle(screen, red, (xnode.point[0]+10, xnode.point[1]+10), 2) i = 0 while i < 8: if i == 0: ynode = Node((xnode.point[0],xnode.point[1]-20), xnode, xnode.d+2, 0) elif i == 1: ynode = Node((xnode.point[0],xnode.point[1]+20), xnode, xnode.d+2, 0) elif i == 2: ynode = Node((xnode.point[0]-20,xnode.point[1]), xnode, xnode.d+2, 0) elif i == 3: ynode = Node((xnode.point[0]+20,xnode.point[1]), xnode, xnode.d+2, 0) elif i == 4: ynode = Node((xnode.point[0]-20,xnode.point[1]-20), xnode, xnode.d+3, 0) elif i == 5: ynode = Node((xnode.point[0]+20,xnode.point[1]-20), xnode, xnode.d+3, 0) elif i == 6: ynode = Node((xnode.point[0]+20,xnode.point[1]+20), xnode, xnode.d+3, 0) elif i == 7: ynode = Node((xnode.point[0]-20,xnode.point[1]+20), xnode, xnode.d+3, 0) if mode == 0: evaluation_Astar(ynode, goalPoint) elif mode == 1: evaluation_Dijkstra(ynode, goalPoint) i += 1 for i in range(0, len(openlist)-1): for j in range(0, len(openlist)-1-i): if mode == 0: data_j = openlist[j].f data_j1 = openlist[j+1].f elif mode == 1: data_j = openlist[j].d data_j1 = openlist[j+1].d if data_j > data_j1: temp = openlist[j] openlist[j] = openlist[j+1] openlist[j+1] = temp pygame.display.flip() for i in range(0, len(openlist)): print(str(openlist[i].point)+"\t--- d = "+str(openlist[i].d)+" & f = "+str(openlist[i].f)) print("parent:"+str(openlist[i].parent.point)) print("-------------------") time.sleep(delay_sec) if len(openlist) == 0: print('False to find the path') elif currentState == 'goalFound': if flag == 1: print('goalFound!!!!!!') currNode = goalNode.parent print("******************") print("startPoint = "+(str(initialPoint.point))) print("goalPoint = "+(str(goalPoint.point))) print("******************") for i in range(0, len(closelist)): print(str(closelist[i].point)+"\t--- d = "+str(closelist[i].d)+" & f = "+str(closelist[i].f)) if i > 0: print("parent:"+str(closelist[i].parent.point)) while currNode.parent != None: pygame.draw.rect(screen, green, (currNode.point, (20, 20))) text_display(str(currNode.d), (currNode.point, (20, 20)), black, 15) currNode = currNode.parent flag = 0 pygame.display.flip() time.sleep(float(delay_sec)/2) fpsClock.tick(10) #处理鼠标事件 for event in pygame.event.get(): if event.type == pygame.QUIT or (event.type == KEYUP and event.key == K_ESCAPE): sys.exit() if event.type == MOUSEBUTTONDOWN: if currentState == 'init': rect = judge_in_grid(event.pos) if initPoseSet == False: if collides(event.pos) == False: initialPoint = Node(rect[0], None, 0, 0) pygame.draw.rect(screen, red, rect) text_display("S",rect, black, 32) initPoseSet = True elif goalPoseSet == False: if collides(event.pos) == False: if rect[0] != initialPoint.point: goalPoint = Node(rect[0],None, 0, 0) print("******************") print("startPoint = "+(str(initialPoint.point))) print("goalPoint = "+(str(goalPoint.point))) print("******************") if mode == 0: initialPoint.f = initialPoint.d+0.1*Manhattan(goalPoint.point, initialPoint.point) openlist.append(initialPoint) pygame.draw.rect(screen, orange, rect) text_display("G",rect, black, 32) goalPoseSet = True currentState = 'lookingForGoal' else: currentState = 'init' initPoseSet = False goalPoseSet = False openlist = [] closelist = [] reset() init_grid() pygame.display.flip() if __name__ == '__main__': run_game()